package com.tgy.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 12/7/20 11:23 AM
 *
 * https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
 */
public class 剑指_Offer_07_重建二叉树_02 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        if (preorder == null || inorder == null || preorder.length != inorder.length) {

            return null;
        }

        TreeNode rootNode = new TreeNode(preorder[0]);

        Stack<TreeNode> stack = new Stack<>();

        stack.push(rootNode);

        int inordeIndex = 0;

        for (int i = 1; i < preorder.length; i++) {

            int nextVal = preorder[i];
            int inordeCur = inorder[inordeIndex];

            TreeNode node = stack.peek();
            if (node.val != inordeCur) {

                node.left = new TreeNode(preorder[i]);
                stack.push(node.left);
            }else {

                TreeNode leftNode = null;
                while (!stack.isEmpty() && stack.peek().val == inorder[inordeIndex]) {

                    leftNode = stack.pop();
                    inordeIndex++;
                }

                leftNode.right = new TreeNode(nextVal);
                stack.push(leftNode.right);
            }
        }

        return rootNode;
    }



}
